package cn.zhl.algorithm._3_并查集.impl;

/**
 * @program: demos
 * @description: 基于size的优化，合并的时候查看两边的根节点下面子元素的个数
 * @author: 刘振华
 * @create: 2020-06-11 19:00
 **/
public class QuickUnionSize extends QuickUnion {
	private int[] sizes;
	public QuickUnionSize(int capacity){
		super(capacity);
		sizes = new int[capacity];
		for(int i = 0;i<capacity;i++){
			sizes[i] = 1;
		}
	}
	@Override
	public int union(int v1, int v2) {
		int oldRoot = find(v1);
		int newRoot = find(v2);
		if(oldRoot == newRoot){
			return oldRoot;
		}
		//比较左右两边的个数多少
		if(sizes[oldRoot]<sizes[newRoot]){
			//左边少，需要将左边指向右边
			parent[oldRoot] = newRoot;
			sizes[newRoot] += sizes[oldRoot];
			return newRoot;
		}else {
			//右边少
			parent[newRoot] = oldRoot;
			sizes[oldRoot] += sizes[newRoot];
			return oldRoot;
		}
	}
}
